package com.tgy.algorithm.base._动态规划;


/**
 *
 */
public class _背包问题 {


    public static int getMaxPackage(int[] weights, int[] values, int rest) {
        return doGetMinPackage(weights,values,0,rest);
    }

    public static int doGetMinPackage(int[] weights,int[] values,int index,int rest) {

        if (index >= weights.length) {
            // 直接返回加入背包的价值为0
            return 0;
        }

        // 不选择当前的weight
        int noAddValue = doGetMinPackage(weights,values,index+1,rest);
        int newRest = rest - weights[index];
        int addValue = 0;
        if (newRest >= 0) {
            addValue = doGetMinPackage(weights,values,index+1,newRest) + values[index];
        }

        return Math.max(noAddValue,addValue);
    }

    public static int getMaxPackage01(int[] weights,int[] values,int bag) {

        int allLen = weights.length;
        int[][] dp = new int[allLen+1][bag+1];

        for (int i = allLen - 1; i >= 0; i--) {
            for (int j = 0; j <= bag; j++) {

                int noAddValue = dp[i+1][j];
                int addValue = 0;
                int newRest = j - weights[i];
                if (newRest >= 0) {
                    addValue = dp[i+1][newRest] + values[i];
                }
                dp[i][j] = Math.max(noAddValue,addValue);
            }
        }

        return dp[0][bag];
    }

    public static void main(String[] args) {
        int[] weights = {2,3,5,7};
        int[] values = {1,5,2,4};
        int minPackage = getMaxPackage(weights, values, 10);
        int maxPackage01 = getMaxPackage01(weights, values, 10);
        System.out.println(minPackage);
        System.out.println(maxPackage01);
    }
}
